extends Object
class_name KDTree

# KDTree的节点
class AgentTreeNode :
	# Agent的开始索引
	var begin : int
	# Agent的结束索引
	var end : int
	# 左叶子节点的AgentTreeNode索引
	var left : int
	# 右叶子节点的AgentTreeNode索引
	var right : int
	# region KDTree节点范围
	var maxX : float
	var maxY : float
	var minX : float
	var minY : float

# KDTree叶子节点的最大尺寸
const MAX_LEAF_SIZE : int = 10
# 本帧的所有代理
var agents : Array[Enemy]
# KDTree的所有节点
var agent_tree : Array[AgentTreeNode]

func build_agent_tree(agents_this_frame : Array[Enemy]) -> void:
	agents = agents_this_frame
	var tree_length : int = 2 * agents.size()
	agent_tree = Array()
	if (agents.size() != 0) :
		build_agent_tree_recursive(0, agents.size(), 0)
	pass

func build_agent_tree_recursive(begin : int, end : int, node : int) -> void:
	var tree_node : AgentTreeNode = agent_tree[node]
	tree_node.begin = begin
	tree_node.end = end
	tree_node.minX = agents[begin].position.x
	tree_node.maxX = agents[begin].position.x
	tree_node.minY = agents[begin].position.y
	tree_node.maxY = agents[begin].position.y
	
	for i in range(begin+1,end) :
		tree_node.maxX = max(tree_node.maxX, agents[i].position.x)
		tree_node.minX = min(tree_node.minX, agents[i].position.x)
		tree_node.maxY = max(tree_node.maxY, agents[i].position.y)
		tree_node.minY = min(tree_node.minY, agents[i].position.y)

		if (end - begin > MAX_LEAF_SIZE) :
			# 节点的宽度大于长度，就竖着划分；否则横着划分
			var isVertical : bool = tree_node.maxX - tree_node.minX > tree_node.maxY - tree_node.minY
			# 取节点的中间值
			var splitValue : float = 0.5 * (tree_node.maxX + tree_node.minX if isVertical else tree_node.maxY + tree_node.minY)

			var left : int = begin
			var right : int = end
			
			# 调整agents数组，找出所有比中间值小的Agent放到数组左边，找出所有比中间值大的Agent放到数组右边
			while (left < right) :
				# 数组左边应该要都小于中间值
				# 从数组左边开始找，找到大于等于中间值的Agent对应的索引
				while (left < right and (agents[left].position.x if isVertical else agents[left].position.y) < splitValue) :
					++left
				
				# 数组右边应该要都大于中间值
				# 从数组右边开始找，找到小于中间值的Agent对应的索引
				while (right > left and (agents[right - 1].position.x if isVertical else agents[right - 1].position.y) >= splitValue) :
					--right
				
				# 将数组左边大于等于中间值的Agent，和数组右边小于中间值的Agent，进行交换
				# 保证左边的Agent一定小于中间值，右边的Agent一定大于等于中间值
				if (left < right) :
					var tempAgent : Enemy = agents[left]
					agents[left] = agents[right - 1]
					agents[right - 1] = tempAgent
					++left
					--right
			
			# KDTree当前节点左孩子管理的Agent数量
			var leftSize : int = left - begin
			if (leftSize == 0) :
				++leftSize
				++left
			
			tree_node.left = node + 1
			tree_node.right = node + 2 * leftSize
			agent_tree[node] = tree_node
			
			build_agent_tree_recursive(begin, left, tree_node.left)
			build_agent_tree_recursive(left, end, tree_node.right)
		else :
			agent_tree[node] = tree_node
